package demo;

public class BSTree {
    //二叉搜索树的根结点开始为空

    private BSTNode root=null;

    //二叉搜索树开始插入元素
    public boolean add(int val){
        //利用传入的数字创建一个结点
        BSTNode node=new BSTNode(val);
       //如果根为空，插入到根上
        if(root==null){
           root=node;
        }
        //当前结点从根结点出发
        BSTNode cur=root;
        //当前结点的父结点
        BSTNode parents=null;
        //当前结点不为空时进入循环
        while(cur!=null){
            if(val==cur.val){
                //二叉搜索树中不允许有相同元素，如有相同，则插入直接失败
                return false;
            }else if(val<cur.val){
                //当前结点走之前，先用父引用标记
                parents=cur;
                //val小了 往左孩子走
                cur=cur.left;
            }else {
                //当前结点走之前，先用父引用标记
                parents=cur;
                ////val小了 往左孩子走
                cur=cur.right;
            }
        }
        //当cur为空是跳出循环，cur==null cur就是插入的位置
        //找出cur是父结点的哪边
        if(val<parents.val){
            //在左孩子，直接指向node
            parents.left=node;
        }else{
            //在右孩子，直接指向node
            parents.right=node;
        }
        return true;
    }
}
